package 图;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

public class 图 {
	
	public static void main(String[] args) {
		//创建图
		
		//使用5个字母创建图
		String Vertexs[] = {"A","B","C","D","E"};
		Graph graph = new Graph(Vertexs.length);
		//循环添加结点
		for(String str : Vertexs) {
			graph.insertVertex(str);
		}
		//添加边 A-B A-C B-C B-D B-E
		/*
		 *           B————E
		 *         / |\ 
		 *        C  | \ 
		 *         \ |  \
		 *           A   D
		 */
		graph.insertEdges(0, 1, 1);
		graph.insertEdges(0, 2, 1);
		graph.insertEdges(1, 2, 1);
		graph.insertEdges(1, 3, 1);
		graph.insertEdges(1, 4, 1);
		
		//输出矩阵
		graph.showGraph();
		
		//深度优先遍历dfs
		//过程：A-B B-C B-D B-E
		graph.dfs();
		
		System.out.println();
		
		//广度优先遍历bfs
		//过程：A-B A-C B-D B-E
		graph.bfs();
		
	}
}

class Graph{
	//Graph

	//存储顶点集合，另一种方法就是单独创建顶点类，然后创建图类，这样顶点中有 值，和访问标志
	private List<String> vertexList;
	//存储图对应的邻接矩阵
	private int[][] edges;
	//表示边的数目
	private int numEdges;
	//表示某个结点是否被访问
	private boolean[] isVisited;
	
	/**
	 *  构造器
	 * @param n 结点个数
	 */
	public Graph(int n) {
		//初始化矩阵
		edges = new int[n][n];
		//初始化结点列表
		vertexList = new ArrayList<String>(n);
		//初始化边个数为0
		numEdges = 0;
		//初始化被访问标记，默认为false
		isVisited = new boolean[n];
	}
	
	/**
	 *  返回结点个数
	 * @return
	 */
	public int getNumVertex() {
		return vertexList.size();
	}
	
	/**
	 *  把两个结点连接起来，并添加边
	 * @param v1 结点的下标，A-0,B-1,C-2...
	 * @param v2 另一个结点下标
	 * @param weight 权值表示连接，1为连接，0为未连接，参数可写可不写，可直接等于1
	 */
	public void insertEdges(int v1, int v2, int weight) {
		//无向图，互相连通
		edges[v1][v2] = weight;
		edges[v2][v1] = weight;
		//添加边
		numEdges++;
	}
	
	/**
	 *  返回改点权值，就是是否连接
	 * @param v1
	 * @param v2
	 * @return
	 */
	public int getWeight(int v1, int v2) {
		return edges[v1][v2];
	}
	
	/**
	 *  添加结点
	 * @param vertex
	 */
	public void insertVertex(String vertex) {
		//
		vertexList.add(vertex);
	}
	
	/**
	 *  返回边的个数
	 * @return
	 */
	public int getNumEdges() {
		return numEdges;
	}
	
	/**
	 * 返回结点下标对应的数据 A-0 B-1 C-2 ...
	 * @param i
	 * @return
	 */
	public String getValueByIndex(int i) {
		return vertexList.get(i);
	}
	
	/**
	 *  显示矩阵
	 */
	public void showGraph() {
		for(int[] arr : edges) {
			System.out.println(Arrays.toString(arr));
		}
	}
	
	/**
	 * 获取第一个邻接结点下标，深度优先：从第一个结点开始遍历，找下一个结点，然后下一个找下下一个
	 * @param index
	 * @return
	 */
	public int getFirstNeighbor(int index) {
		//第一个邻接节点，从这一行第一个开始
		for (int i = 0; i < vertexList.size(); i++) {
			//如果这一行某一个大于1，表示这两个有链接
			if(edges[index][i] > 0) {
				return i;
			}
		}
		//没找到返回-1
		return -1;
	}
	
	/**
	 * 从这个结点开始，向后找下一个连接节点，还是这一行，只不过从某点开始向后找
	 * @param v1
	 * @param v2
	 * @return
	 */
	public int getNextNeighbor(int v1, int v2) {
		//v1 不变，v2像后找
		for(int i = v2 +1; i < vertexList.size(); i++) {
			if(edges[v1][i] > 0) {
				return i;
			}
		}
		return -1;
	}
	
	/**
	 * 深度遍历，从第一个结点开始，找下一个开始，然后接着下一个结点再找下下个
	 * @param isVisited 是否被访问
	 * @param i 开始结点
	 */
	public void dfs(boolean[] isVisited, int i) {
		//首先输出结点
		System.out.print(getValueByIndex(i)+"->");
		//将结点设为已访问
		isVisited[i] = true;
		//查找i的第一个邻接节点，初始从0开始
		int first = getFirstNeighbor(i);
		//找到就进去
		while(first != -1) {
			//且没被访问
			if(!isVisited[i]) {
				//继续向后遍历
				dfs(isVisited,i);
			}
			//如果被访问，行不变，从这个点向后继续找下一个邻接结点
			first = getNextNeighbor(i, first);
		}
	}
	
	/**
	 * 深度优先遍历
	 * 重载dfs，遍历所有结点，因为上面那个只能找到邻接结点，如果走到尽头，需要返回上一层继续遍历
	 */
	public void dfs() {
		//初始化访问标记，isVisited
		isVisited = new boolean[vertexList.size()];
		//遍历所有结点
		for (int i = 0; i < getNumVertex(); i++) {
			//从第一个开始，如果这一层找完，就返回找第二层，直到找全
			if(!isVisited[i]) {
				//回溯
				dfs(isVisited, i);
			}
		}
	}
	
	/**
	 * 广度优先遍历，一层层遍历
	 * @param isVisited
	 * @param i
	 */
	public void bfs(boolean[] isVisited, int i) {
		//表示队列头结点下标
		int u;
		//邻接结点
		int w;
		//队列，记录结点访问顺序
		LinkedList<Integer> queue = new LinkedList<>();
		
		//访问结点，输出
		System.out.print(getValueByIndex(i)+"->");
		//标记已访问
		isVisited[i] = true;
		//将节点加入队列，添加一个结点，就把这一层全访问完，然后取出队列，从下一个队列头开始
		queue.addLast(i);
		
		while(!queue.isEmpty()) {
			//取出队列头结点下标
			u = queue.removeFirst();
			//得到第一个邻接结点的下标w
			w = getFirstNeighbor(u);
			//找到
			while(w != -1) {
				//未访问
				if(!isVisited[w]) {
					//输出
					System.out.print(getValueByIndex(w)+"->");
					//标记已访问
					isVisited[w] = true;
					//入队
					queue.addLast(w);
				}
				//已访问，跳过，找下一个，还是这一层
				w = getNextNeighbor(u, w);
			}
		}
	}
	
	/**
	 * 广度优先遍历，重载
	 */
	public void bfs() {
		//初始化访问标记
		isVisited = new boolean[vertexList.size()];
		//遍历每一个
		for (int i = 0; i < getNumVertex(); i++) {
			if(!isVisited[i]) {
				bfs(isVisited, i);
			}
		}
	}
	
}